home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / BYACC__ / SYMTAB.C < prev    next >
C/C++ Source or Header  |  1989-11-19  |  5KB  |  312 lines
  1. #include <assert.h>
  2. #include <stdio.h>
  3. #include "defs.h"
  4. #include "new.h"
  5. #include "symtab.h"
  6. #include "tokens.h"
  7.  
  8. #define    TABLE_SIZE    1009
  9.  
  10. bucket **symtab;
  11. bucket *first_symbol;
  12. bucket *last_symbol;
  13.  
  14. int
  15. compare(f, s, m, g, t, n)
  16. int f, g;
  17. register char *s, *t;
  18. int m, n;
  19. {
  20.   register int i;
  21.   register int c1, c2;
  22.   register int result;
  23.  
  24.   result = 0;
  25.   for (i = ( m < n ? m : n ); i > 0 && result == 0; i--)
  26.     if ((c1 = *s++) != (c2 = *t++)) result = c1 - c2;
  27.  
  28.   if (result == 0)
  29.     {
  30.       result = m - n;
  31.       if (result == 0) result = f - g;
  32.     }
  33.  
  34.   return (result);
  35. }
  36.  
  37. int
  38. hash(str, len)
  39. char *str;
  40. int len;
  41. {
  42.     register char *s;
  43.     register int i, n;
  44.  
  45.     assert(str && len > 0);
  46.     s = str;
  47.     n = *s;
  48.     i = len;
  49.     while (--i > 0)
  50.     {
  51.     n = 31*n + *s++;
  52.     while (n >= TABLE_SIZE) n -= TABLE_SIZE;
  53.     }
  54.  
  55.     return (n);
  56. }
  57.  
  58. char *
  59. mk_prname(form, key, length)
  60. int form;
  61. register char *key;
  62. int length;
  63. {
  64.   register int i, k;
  65.   register int c;
  66.   register int close_quote;
  67.   register char *name;
  68.  
  69.   if (form == IDENTIFIER)
  70.     k = 1;
  71.   else
  72.     k = 3;
  73.   for (i = 0; i < length; i++)
  74.     {
  75.       c = key[i];
  76.       switch (c)
  77.     {
  78.     case NEWLINE:
  79.     case CR:
  80.     case QUOTE:
  81.     case DOUBLE_QUOTE:
  82.     case BACKSLASH:
  83.     case HT:
  84.     case VT:
  85.     case BS:
  86.     case FF:
  87.       k += 2;
  88.  
  89.     default:
  90.       if (PRINTABLE(c))
  91.         k++;
  92.       else
  93.         k += 4;
  94.     }
  95.     }
  96.  
  97.   name = NEW2(k, char);
  98.   switch (form)
  99.     {
  100.     case IDENTIFIER:
  101.       k = 0;
  102.       close_quote = NUL;
  103.       break;
  104.  
  105.     case CHARACTER:
  106.       name[0] = QUOTE;
  107.       k = 1;
  108.       close_quote = QUOTE;
  109.       break;
  110.  
  111.     case STRING:
  112.       name[0] = DOUBLE_QUOTE;
  113.       k = 1;
  114.       close_quote = DOUBLE_QUOTE;
  115.       break;
  116.  
  117.     case TYPE_IDENTIFIER:
  118.       name[0] = '<';
  119.       k = 1;
  120.       close_quote = '>';
  121.       break;
  122.  
  123.     default:
  124.       panic("mk_prname");
  125.     }
  126.  
  127.   for (i = 0; i < length; i++)
  128.     {
  129.       c = key[i];
  130.       switch (c)
  131.     {
  132.     case NEWLINE:
  133.       name[k] = BACKSLASH;
  134.       name[k+1] = 'n';
  135.       k += 2;
  136.       break;
  137.  
  138.     case CR:
  139.       name[k] = BACKSLASH;
  140.       name[k+1] = 'r';
  141.       k += 2;
  142.       break;
  143.  
  144.     case QUOTE:
  145.     case DOUBLE_QUOTE:
  146.     case BACKSLASH:
  147.       name[k] = BACKSLASH;
  148.       name[k+1] = c;
  149.       k += 2;
  150.       break;
  151.  
  152.     case HT:
  153.       name[k] = BACKSLASH;
  154.       name[k+1] = 't';
  155.       k += 2;
  156.       break;
  157.  
  158.     case VT:
  159.       name[k] = BACKSLASH;
  160.       name[k+1] = 'v';
  161.       k += 2;
  162.       break;
  163.  
  164.     case BS:
  165.       name[k] = BACKSLASH;
  166.       name[k+1] = 'b';
  167.       k += 2;
  168.       break;
  169.  
  170.     case FF:
  171.       name[k] = BACKSLASH;
  172.       name[k+1] = 'f';
  173.       k += 2;
  174.       break;
  175.  
  176.     default:
  177.       if (PRINTABLE(c))
  178.         {
  179.           name[k] = c;
  180.           k++;
  181.         }
  182.       else
  183.         {
  184.           name[k] = BACKSLASH;
  185.           name[k+1] = ((c >> 6) & 3) + '0';
  186.           name[k+2] = ((c >> 3) & 7) + '0';
  187.           name[k+3] = (c & 7) + '0';
  188.           k += 4;
  189.         }
  190.     }
  191.     }
  192.  
  193.   name[k] = close_quote;
  194.   return (name);
  195. }
  196.  
  197. bucket *
  198. make_bucket(form, key, length)
  199. int form;
  200. char *key;
  201. int length;
  202. {
  203.   register int i;
  204.   register char *s, *t;
  205.   register bucket *bp;
  206.  
  207.   bp = NEW(bucket);
  208.   bp->length = length;
  209.   bp->key = s = NEW2(length + 1, char);
  210.   bp->prname = mk_prname(form, key, length);
  211.   bp->value = UNDEFINED;
  212.   t = key;
  213.   for (i = length; i > 0; i--)
  214.     *s++ = *t++;
  215.   bp->form = form;
  216.   if (form == CHARACTER || form == STRING)
  217.     bp->class = TERMINAL;
  218.  
  219.   last_symbol->next = bp;
  220.   last_symbol = bp;
  221.  
  222.   return (bp);
  223. }
  224.  
  225. tabinit()
  226. {
  227.   register int i;
  228.   register bucket *bp;
  229.  
  230.   symtab = NEW2(TABLE_SIZE, bucket *);
  231.   for (i = 0; i < TABLE_SIZE; i++)
  232.     symtab[i] = NIL(bucket);
  233.  
  234.   bp = NEW(bucket);
  235.   bp->length = 5;
  236.   bp->key = mk_prname(IDENTIFIER, "error", 5);
  237.   bp->prname = mk_prname(IDENTIFIER, "error", 5);
  238.   bp->value = UNDEFINED;
  239.   bp->index = 1;
  240.   bp->form = IDENTIFIER;
  241.   bp->class = TERMINAL;
  242.   bp->used = 1;
  243.  
  244.   first_symbol = bp;
  245.   last_symbol = bp;
  246.   symtab[hash(bp->key, 5)] = bp;
  247. }
  248.  
  249. bucket *
  250. lookup(form, key, length)
  251. int form;
  252. char *key;
  253. int length;
  254. {
  255.   register int cc, hash_value;
  256.   register bucket *bp, *tbp;
  257.  
  258.   hash_value = hash(key, length);
  259.   bp = symtab[hash_value];
  260.  
  261.   if (bp == NIL(bucket))
  262.     symtab[hash_value] = bp = make_bucket(form, key, length);
  263.   else
  264.     {
  265.       for (;;)
  266.     {
  267.       if (cc = compare(form, key, length, bp->form, bp->key, bp->length))
  268.         {
  269.           tbp = bp;
  270.           if (cc < 0)
  271.         {
  272.               bp = bp->left;
  273.           if (bp == NIL(bucket))
  274.             {
  275.               tbp->left = bp = make_bucket(form, key, length);
  276.               break;
  277.             }
  278.         }
  279.           else
  280.         {
  281.               bp = bp->right;
  282.           if (bp == NIL(bucket))
  283.             {
  284.               tbp->right = bp = make_bucket(form, key, length);
  285.               break;
  286.             }
  287.         }
  288.         }
  289.       else
  290.         break;
  291.     }
  292.     }
  293.  
  294.   return (bp);
  295. }
  296.  
  297. free_symtab()
  298. {
  299.   register bucket *bp, *tbp;
  300.  
  301.   bp = first_symbol;
  302.   while (bp)
  303.     {
  304.       tbp = bp->next;
  305.       FREE(bp->key);
  306.       FREE(bp);
  307.       bp = tbp;
  308.     }
  309.  
  310.   FREE(symtab);
  311. }
  312.